package map.DSU;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class DSU {
    private int[] father;
    public void init(int n){
        father = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }
    public int find(int u) {
        if (u == father[u]){
            return u;
        } else {
            return find(father[u]);
        }
    }
    public void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u != v){
            father[u] = v;
        }
    }
    public boolean isSame(int u, int v){
        return find(u) == find(v);
    }
}
